/**
 * @author LKQ
 * @date 2022/1/28 14:26
 * @description 由题意，可以先反转，然后双指针
 */
public class Solution {
    public static void main(String[] args) {
        ListNode l = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
        Solution solution = new Solution();
        solution.reorderList(l);
    }

    public void reorderList(ListNode head) {

        // 首先进行反转
        ListNode p = new ListNode(0, head);
        ListNode q = reverse(p.next);
        ListNode ans = new ListNode(0);
        boolean is = true;
        while (p != null) {
            ListNode temp1 = is ? p : q;
            ans.next = temp1;
            ans = temp1;
            if (is) {
                p = p.next;
                is = false;
            }else {
                q = q.next;
                is = true;
            }
        }
        head = ans.next;
    }
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
         }
        return prev;
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
